数位DP windy数

发表于 | 评论数： | 阅读次数：

又到了一年一度的DP欢乐时刻~ 虽然我是一只蒟蒻~ 爆蛋味让我变得更香~ 咳咳

首先是入门题：windy数 https://www.luogu.org/problemnew/show/P2657

这我就不会做了啊喂！！！ 仔细回味yzc大佬讲的，恍然大悟之打开题解

原来真是模板

先让我们来看看数位DP

数位dp一般应用于：

求出在给定区间[A,B]内，符合条件P(i)的数i的个数.

条件P(i)一般与数的大小无关，而与 数的组成 有关.

一般来说讯问[A，B]区间内满足要求的数的个数，拆成[1,A-1]，[1,B]来做

模板~：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//    pos    = 当前处理的位置(一般从高位到低位)
//    pre    = 上一个位的数字(更高的那一位)
//    status = 要达到的状态,如果为1则可以认为找到了答案,到时候用来返回,
//         　　 给计数器+1。
//    limit  = 是否受限,也即当前处理这位能否随便取值。如567,当前处理6这位,
//         　　 如果前面取的是4,则当前这位可以取0-9。如果前面取的5,那么当前
//         　　 这位就不能随便取，不然会超出这个数的范围,所以如果前面取5的
//         　　 话此时的limit=1,也就是说当前只可以取0-6。
//
//    用DP数组保存这三个状态是因为往后转移的时候会遇到很多重复的情况。
int    dfs(int pos,int pre,int status,int limit)
{
    //已结搜到尽头,返回"是否找到了答案"这个状态。
    if(pos < 1)
        return    status;

    //DP里保存的是完整的,也即不受限的答案,所以如果满足的话,可以直接返回。
    if(!limit && DP[pos][pre][status] != -1)
        return    DP[pos][pre][status];

    int    end = limit ? DIG[pos] : 9;
    int    ret = 0;
    
    //往下搜的状态表示的很巧妙,status用||是因为如果前面找到了答案那么后面
    //还有没有答案都无所谓了。而limti用&&是因为只有前面受限、当前受限才能
    //推出下一步也受限，比如567,如果是46X的情况,虽然6已经到尽头,但是后面的
    //个位仍然可以随便取,因为百位没受限,所以如果个位要受限,那么前面必须是56。
    //
    //这里用"不要49"一题来做例子。
    for(int i = 0;i <= end;i ++)
        ret += dfs(pos - 1,i,status || (pre == 4 && i == 9),limit && (i == end));

    //DP里保存完整的、取到尽头的数据
    if(!limit)
        DP[pos][pre][status] = ret;

    return    ret;
}

然后回到这道题：要求A,B间相邻每位绝对值大于2的数的个数

定义状态，$f[i][j]$ 表示i位的数最高位为j的方案数，根据上文所述，首先解决1~A-1范围内的数

先十进制分解(A-1)，所有位数低于他的显然被包括，所有位数相同且最高位小于他的显然被包括

那么剩下的就一位一位枚举即可，最后1~B同理可得

$Code:$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
#define int long long
int A,B,f[12][10];
int solve(int x)
{
	int a[12],len=0,res=0;
	while(x)
	{
		a[++len]=x%10;
		x/=10;
	}
	for(int i=1;i<len;i++)
		for(int j=1;j<=9;j++)
			res+=f[i][j];
	for(int i=1;i<a[len];i++)res+=f[len][i];
	for(int i=len-1;i>=1;i--)
	{
		for(int j=0;j<a[i];j++)
			if(abs(j-a[i+1])>=2)res+=f[i][j];
		if(abs(a[i+1]-a[i])<2)break;
	}
	return res;
}
signed main()
{
	scanf("%lld%lld",&A,&B);
	if(A>B)swap(A,B);
	for(int i=0;i<=9;i++)f[1][i]=1;
	for(int i=2;i<=10;i++)
		for(int j=0;j<=9;j++)
			for(int k=0;k<=9;k++)
				if(abs(j-k)>=2)f[i][j]+=f[i-1][k];
	printf("%lld\n",solve(B+1)-solve(A));
}

撒fafa~